#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>

using namespace std;

// problem 1
bool all_unique(const char* str) {
  if (str) {
    vector<size_t> used(1 << 8, 0);
    for (const char* p = str; *p != '\0'; ++p) {
      used[(size_t) *p] += 1;
    }
    for (const char* p = str; *p != '\0'; ++p) {
      if (used[(size_t) *p] > 1)
	return false;
    }
  }
  return true;
}

bool all_unique_no_buffer(const char* str) {
  if (str) {
    size_t len = strlen(str);
  
    for (size_t i = 0; i < len; i++) {
      for (size_t j = i+1; j < len; j++) {
	if (str[i] == str[j]) 
	  return false;
      }
    }
  }
  return true;
}

// problem 2
char* reverse_str(char* str) {
  if (str) {
    size_t len = strlen(str);
    size_t left = 0;
    size_t right = len-1;
    while (left < right) {
      swap(str[left++], str[right--]);
    }
  }
  return str;
}

// problem 3
char* remove_duplicate_no_buffer(char* str) {
  if (str) {
    size_t len = strlen(str);
    // mark duplicate chars as '\0'
    for (size_t i = 0; i < len; ++i) {
      for (size_t j = i+1; j < len; ++j) {
	if (str[i] == str[j])
	  str[j] = '\0';
      }
    }

    // shift chars to left
    for (size_t open = 0, cur = 0; cur < len; ++cur) {
      if (str[cur] != '\0')
	swap(str[open++], str[cur]);
    }
  }
  return str;
}

// problem 4
bool anagrams(const char* str1, const char* str2) {
  size_t len1 = strlen(str1);
  size_t len2 = strlen(str2);

  if (len1 != len2) 
    return false;

  char* op1 = new char[len1+1];
  strcpy(op1, str1);
  char* op2 = new char[len2+1];
  strcpy(op2, str2);

  sort(op1, op1+len1);
  sort(op2, op2+len2);

  bool ret = true;
  for (size_t i = 0; i < len1; i++) {
    if (op1[i] != op2[i]) {
      ret = false;
      break;
    }
  }
  delete [] op1;
  delete [] op2;

  return ret;
}

bool anagrams_with_buffer(const char* str1, const char* str2) {
  size_t len1 = strlen(str1);
  size_t len2 = strlen(str2);

  if (len1 != len2) 
    return false;

  vector<int> cnt(1 << 8, 0);
  for (size_t i = 0; i < len1; i++) {
    cnt[(size_t) str1[i]]++;
    cnt[(size_t) str2[i]]--;
  }

  for (size_t i = 0; i < cnt.size(); i++) {
    if (cnt[i] != 0)
      return false;
  }
  return true;
}

// problem 5
// skipped.

// problem 6
template<size_t n>
void rotate_matrix(int matrix[n][n]) {
  if (matrix) {
    for (size_t layer = 0; layer < n/2; layer++) {
      size_t first = layer;
      size_t last = n - layer;

      for (size_t i = first; i < last-1; i++) {
	size_t offset = i - first;
	// save cell on the top
	int val = matrix[first][first+offset];
	// left -> top
	//cout << last-1-offset << "," << first << "->" << first << "," << first+offset << endl;
	matrix[first][first+offset] = matrix[last-1-offset][first];
	// bottom -> left
	//cout << last-1 << "," << last-1-offset << "->" << last-1-offset << "," << first << endl;
	matrix[last-1-offset][first] = matrix[last-1][last-1-offset];
	// right -> bottom
	//cout << first+offset << "," << last-1 << "->" << last-1 << "," << last-1-offset << endl;
	matrix[last-1][last-1-offset] = matrix[first+offset][last-1];
	// top -> right
	//cout << first << "," << first+offset << "->" << first+offset << "," << last-1 << endl;
	matrix[first+offset][last-1] = val;
      }
    }
  }
}

template<size_t m, size_t n>
void print(int matrix[m][n]) {
  if (matrix) {
    for (size_t r = 0; r < m; r++) {
      for (size_t c = 0; c < n; c++) {
	cout << matrix[r][c] << " ";
      }
      cout << endl;
    }
  }
}

// problem 7
template<size_t m, size_t n>
void zeros(int matrix[m][n]) {
  if (matrix) {
    vector<bool> rows(m, false);
    vector<bool> cols(n, false);

    for (size_t r = 0; r < m; r++) {
      for (size_t c = 0; c < n; c++) {
	if (matrix[r][c] == 0) {
	  rows[r] = true;
	  cols[c] = true;
	}
      }
    }

    for (size_t r = 0; r < m; r++) {
      if (rows[r]) {
	for (size_t c = 0; c < n; c++)
	  matrix[r][c] = 0;
      }
    }

    for (size_t c = 0; c < n; c++) {
      if (cols[c]) {
	for (size_t r = 0; r < m; r++) 
	  matrix[r][c] = 0;
      }
    }
  }
}

// problem 8
bool rotation_str(const string str1, const string str2) {
  string str = str1 + str1;
  if (str.find(str2) == string::npos)
    return false;
  return true;
}

int main() {
  cout << "Problem 1: " << endl;
  cout << "Test all unique with additional data structure" << endl;
  cout << "abdcea : " << all_unique("abdcea") << endl;
  cout << "abdce : " << all_unique("abdce") << endl;
  cout << "Test all unique without additional data structure" << endl;
  cout << "abdcea : " << all_unique_no_buffer("abdcea") << endl;
  cout << "abdce : " << all_unique_no_buffer("abdce") << endl;
  cout << endl;

  cout << "Problem 2: " << endl;
  cout << "Test c-style string reverse" << endl;
  char str[] = "abcdefg";
  cout << reverse_str(str) << endl;
  cout << endl;

  cout << "Problem 3: " << endl;
  cout << "Test remove duplicate chars with no buffer" << endl;
  char dups[] = "abcadba";
  char alldups[] = "aaaa";
  cout << remove_duplicate_no_buffer(str) << endl;
  cout << remove_duplicate_no_buffer(dups) << endl;
  cout << remove_duplicate_no_buffer(alldups) << endl;
  cout << endl;

  cout << "Porlbme 4: " << endl;
  cout << "Test two strings are anagrams" << endl;
  cout << anagrams("abacd", "aadcb") << " == 1" << endl;
  cout << anagrams("abacd", "abacc") << " == 0" << endl;
  cout << anagrams_with_buffer("abacd", "aadcb") << " == 1" << endl;
  cout << anagrams_with_buffer("abacd", "abacc") << " == 0" << endl;
  cout << endl;
  
  cout << "Problem 5: " << endl;
  cout << "Test replace space with %20" << endl;
  cout << "Skippd. Not a good C++ interview question." << endl;
  cout << endl;

  cout << "Problem 6: " << endl;
  cout << "Test rotate matrix" << endl;
  int matrix[2][2] = {{1,2},{3,4}};
  print<2,2>(matrix); cout << endl;
  rotate_matrix<2>(matrix);
  print<2,2>(matrix); cout << endl;
  
  int matrix1[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
  print<3,3>(matrix1); cout << endl;
  rotate_matrix<3>(matrix1);
  print<3,3>(matrix1); cout << endl;

  cout << "Problem 7: " << endl;
  cout << "Test set zeros in matrix" << endl;
  cout << "no zeors in matrix" << endl;
  print<3,3>(matrix1); cout << endl;
  zeros<3,3>(matrix1);
  print<3,3>(matrix1); cout << endl;

  cout << "some zero in matrix" << endl;
  matrix1[2][2] = 0;
  print<3,3>(matrix1); cout << endl;
  zeros<3,3>(matrix1);
  print<3,3>(matrix1); cout << endl;

  cout << "should be all zero matrix" << endl;
  print<3,3>(matrix1); cout << endl;
  zeros<3,3>(matrix1);
  print<3,3>(matrix1); cout << endl;
  
  cout << "Problem 8: " << endl;
  cout << "Test rotation string" << endl;
  cout << rotation_str("abcde", "cdeab") << " == 1" << endl;
  cout << rotation_str("abcde", "cdeba") << " == 0" << endl;
  
  return 0;
}
